package com.major.algorithm.dynamicprograming;

import java.util.Arrays;

public class Knapsack {
    public static void main(String[] args) {
        int[] weight = {1, 4, 3};
        int[] value = {1500, 3000, 2000};
        int content = 4;            // 容量
        int num = value.length;     // 商品个数

        // 表示在前i个物品中能够装入容量为j的背包中的 最大价值
        int[][] maxVal = new int[num + 1][content + 1];
        int[][] path = new int[num + 1][content + 1];

        for (int i = 0; i < maxVal.length; i++) {
            maxVal[i][0] = 0;
        }
        Arrays.fill(maxVal[0], 0);

        for (int i = 1; i < maxVal.length; i++) {
            for (int j = 1; j < maxVal[0].length; j++) {
                // 如果所加入物品容量 大于 当前容量 ，直接采取上一单元格的策略
                if (weight[i - 1] > j) {//--------------------------------------------> 这两个i-1 表示，当前物品的重量
                    maxVal[i][j] = maxVal[i - 1][j];                //   其它的i，j表示在表中的位置        ↑
                                                                                        //             |
                    // 所加入物品容量 <= 当前容量                                           //             |
                } else {        //  可以选择    ↑ 不加       或者       ↑ 加                              |
                    maxVal[i][j] = Math.max(maxVal[i - 1][j], value[i - 1] + maxVal[i - 1][j - weight[i - 1]]);
                }
            }
        }

        for (int[] ints : maxVal) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }

    }
}
